package Tree;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class L297_二叉树序列化与反序列化 {
}

class AVCodec {
    // Encodes a tree to a single string.
    //BST的前序遍历结果
    public String serialize(TreeNode root) {
        if (root == null) return "";
        StringBuilder sb = new StringBuilder();
        helper(root, sb);
        return sb.substring(0, sb.length() - 1);
    }

    private void helper(TreeNode root, StringBuilder sb) {
        if (root == null) return;//这里直接返回了，没有做null的添加
        //拼接当前节点
        sb.append(root.val).append(",");
        helper(root.left, sb);
        helper(root.right, sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null || data.length() == 0) return null;
        String[] arr = data.split(",");
        return builder(arr, 0, arr.length - 1);
    }

    private TreeNode builder(String[] arr, int lo, int hi) {
        if (lo > hi) return null;
        TreeNode root = new TreeNode(Integer.valueOf(arr[lo]));
        //找到第一个比首元素大的元素位置
        int index = hi + 1;
        for (int i = lo + 1; i <= hi; i++) {
            if (Integer.valueOf(arr[i]) > root.val) {
                index = i;
                break;
            }
        }
        //递归构建子树
        root.left = builder(arr, lo + 1, index - 1);
        root.right = builder(arr, index, hi);
        return root;
    }
}


/**
 * 这题和二叉搜索树不一样的地方，普通二叉树，空指针用null来确定，所以能够恢复
 *
 * 二叉搜索树要求不能有null，就要给反序列化，二叉树搜索树是有特性的，能恢复
 */
class Codec {
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        ser_rec(root, sb);
        return sb.toString();
    }

    void ser_rec(TreeNode root, StringBuilder sb){
        if(root == null){
            sb.append("null,");
            return;
        }
        sb.append(root.val + ",");
        ser_rec(root.left, sb);
        ser_rec(root.right, sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] tmp = data.split(",");
        List<String> list = Arrays.asList(tmp);
        return des_rec(new ArrayList<>(list));
    }

    //这个反序列化很巧妙
    TreeNode des_rec(List<String> list){
        TreeNode root;
        if(list.get(0).equals("null")){//对空节点的处理很重要
            list.remove(0);//这两个remove要记得
            return null;
        }

        root = new TreeNode(Integer.parseInt(list.get(0)));
        list.remove(0);//这两个remove要记得
        root.left = des_rec(list);
        root.right = des_rec(list);

        return root;
    }
}